COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00014 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a07.tex[154,phy] \today\hfill}

\newdimen\unit
\def\point#1 #2 {\rlap{\kern#1\unit
  \raise#2\unit\hbox to 0\unit{\hss$\scriptstyle\bullet$\hss}}}
\def\ycoord#1 {\rlap{\kern -0.2\unit
 \raise#1\unit\hbox{#1}}}
\def\xcoord#1 {\rlap{\kern#1\unit
 \lower0.2\unit\hbox to 0\unit
 {\hss #1\hss}}}


\bigskip

\noindent{\bf Quantifiers, Universal and Existential.}

Many of the results of mathematical language theory are stated in a
maze of quantifiers; in the Pumping Lemma for context-free languages,
there are five. Most students are unaccustomed to using accurately
heavily quantified results. It may help to see them as statements
about a game.

The formula $\forall x\,P(x)$ means that even if someone {\it trying\/}
to make $P(x)$ false chooses~$x$, $P(x)$ still comes out true. The
formula $\exists y\,P(y)$ means that if someone trying to make $P(y)$
true makes the correct choice of~$y$, $P(y)$ is true. These two
formulations can be combined to interpret formulas where the
quantifiers are nested.

If $P(x,y)$ is a relation over a finite domain, we can show in a
table the values for $\langle x,y\rangle$ that make $P(x,y)$
true. Suppose $P(x,y)$ has this table:

$$\vbox{\tabskip=0pt\offinterlineskip
\halign{$\ctr{#}$&$\ctr{#}$&$\ctr{#}$&\vrule#&\strut\quad$\ctr{#}$\quad
&$\ctr{#}$\quad&$\ctr{#}$\quad&$\ctr{#}$\quad&$\ctr{#}$\cr
&&y\cr
x&&&\omit&1&2&3&4&5\cr
\noalign{\smallskip}
&&&\omit&\multispan5\hrulefill\cr
&&&height 2pt\cr
&1&&&&\ast&&&\ast\cr
&2&&&&&&\ast&\ast\cr
&3&&&&&&\ast&\ast\cr
&4&&&&\ast&\ast&\ast\cr
&5&&&&\ast\cr}}$$

\bigskip
\disleft 20pt:$\bullet$:
$(\forall x)(\forall y)\,P(x,y)$ means that even if someone trying to make
$P(x,y)$ false gets to choose both $x$ and~$y$, $P(x,y)$ still comes out
true. But here the adversary can choose $x=1$, $y=4$, say, and make
$P(1,4)$ false, so $(\forall x)(\forall y)\,P(x,y)$ is not true of
this relation. It would only be true if every entry of the table were
filled in.

\smallskip
\disleft 20pt:$\bullet$:
$(\exists x)(\exists y)\,P(x,y)$ means that if someone trying to
make $P(x,y)$ true makes the correct choice, first of~$x$, then of~$y$,
$P(x,y)$ is true. Here it can be done by choosing $x=4$, $y=3$, say.
It is true if there is even a single mark in the table.

\smallskip
\disleft 20pt:$\bullet$:
$(\forall x)(\exists y)\,P(x,y)$ means that even if someone trying to make
$P(x,y)$ false chooses~$x$, someone trying to make $P(x,y)$ true
can choose $y$ to make $P(x,y)$ true. The choice of $y$ is made
after $x$ has been chosen. Here if $x=5$, $y$ is chosen to be~2; if
$x=3$, however, $y$~must be 4 or~5. The quantified formula is true
if there is a mark in every horizontal row of the table.

\smallskip
\disleft 20pt:$\bullet$:
$(\exists y)(\forall x)\,P(x,y)$ means that someone trying to make
$P(x,y)$ true can choose $y$ so that, even if an opponent then chooses~$x$,
$P(x,y)$ comes out true. In this example, no choice of $y$ is good
enough. If I choose $y=2$, my opponent chooses $x=2$ or~3. If I choose
$y=5$, my opponent chooses $x=4$ or~5. The important difference in
the order of the quantifiers is reflected in the order of the choices
in the game. Putting the $\exists y$ quantifier early means that I~have
to choose $y$ before I~know what $x$ is; this gives my opponent the
advantage. This formula is only true of $P$ if there is a completely
marked vertical column in the table.

\smallskip
\disleft 20pt:$\bullet$:
$(\forall y)(\exists x)\,P(x,y)$ and $(\exists x)(\forall y)\,P(x,y)$.
The reader should confirm that neither of these is true. What would the
table have to be like to make them true?

\smallskip
We can treat any quantified formula
as a game between players named Al and Izzy; Al gets to choose the
$\forall$~variables, and Izzy gets to choose the $\exists$~variables,
working from left to right. Al tries to make the formula false,
and Izzy tries to make it true. Assuming intelligent play on
both sides, the quantified formula is true if Izzy can win the game.

In the calculus, a function $f$ is continuous if
$$(\forall x)(\forall\epsilon >0)(\exists\delta >0)(\forall y\hbox{ with }
|x-y|<\delta)\,|f(x)-f(y)|<\epsilon\,.$$
The graph below illustrates a continuous function $f$.

$$\vbox{\hbox{\unit=1in
\ycoord 0
\ycoord 1
\xcoord 0
\point 0.5 1
\xcoord 1
\point 1.25 1
\point 1.75 1
\xcoord 2
\point 2.17 1
\point 2.5 1
\point 2.83 1
\xcoord 3
\point 3.12 1
\point 3.38 1
\point 3.62 1
\point 3.88 1
\xcoord 4
\point 4.1 1
\point 0 0
\point 1 0
\point 1.5 0
\point 2 0
\point 2.33 0
\point 2.67 0
\point 3 0
\point 3.25 0
\point 3.5 0
\point 3.75 0
\point 4 0
\point 3.3 0.4
\kern 4.1\unit
}}$$

\bigskip
\noindent In the game that interprets the definition of continuity,
Al picks an~$x$, let's say 3.3 as shown, and a positive vertical range~$\epsilon$,
let's say 0.05. Izzy picks a positive horizontal range~$\delta$. Since
the slope of $f$ near $x=3.3$ is~8, Izzy picks $\delta$ to be no more
than~$\epsilon/8$; $\delta =0.005$ will do. Now Al can't win;
in the range $3.295<y<3.305$, $f(y)$ can't go more than 0.04 above
or below $f(x)=0.4$.
By making Izzy's winning strategy explicit, we can prove $f$ continuous.

The same function is not uniformly continuous, though. The definition
of uniform continuity is:
$$(\forall\epsilon >0)(\exists\delta >0)(\forall x,y\hbox{ with }
|x-y|<\delta)\,|f(x)-f(y)|<\epsilon\,.$$
Now Al picks $\epsilon =1/2$, and even if Izzy picks $\delta =0.01$,
Al can find $x$ and~$y$ within 0.01 of each other, with $f(x)=0$,
$f(y)=1$; $x=100$, $y=99.995$ will do fine. It is now Al who has the
winning strategy, so $f$ does not meet the definition of uniform continuity.

The pumping lemma for regular sets says:

\smallskip
\disleft 30pt::($\forall R\ni R$ is a regular set)
\disleft 30pt::($\exists n$, an integer $≥0$)
\disleft 30pt::($\forall x\in R$, with length$(x)≥n$)
\disleft 30pt::($\exists u,v,w$, with $uvw=x$, length$(uv)≤n$,
length$(v)>0$)
\disleft 30pt::($\forall i≥0$)
\disleft 30pt::$uv↑iw\in R$

\smallskip
\noindent
This represents a game of five moves, where Izzy can win. Al chooses
a regular set, Izzy choose~$n$; a~correct strategy is to let $n$
be the number of states needed to recognize~$R$. Al chooses a string
in~$R$, of length $≥n$; the automaton for~$R$, reading~$x$, then has to
repeat a state. Izzy breaks $x$ up into $u$, $v$,~$w$ so that $u$ and $uv$
are the prefixes of $x$ that put the automaton into the repeated state.
Al now chooses how many times $v$ is pumped, but he can't win; the
automaton for~$R$ will accept $uvvv\ldots vw$.

Let's modify the game by letting Al pick any language. Al picks 
$\{a↑jb↑j\}$. Izzy picks any~$n$. Al picks $x=a↑nb↑n$.
Izzy has to pick $u$, $v$, $w$ with $v=a↑m$, $m>0$. Al picks $i=2$.
Now $uv↑2w=a↑{m+n}b↑n\notin\{a↑jb↑j\}$, and Al has won. The pumping lemma 
says that Izzy could have won if Al had picked a regular set, so we
can infer that Al cheated; $\{a↑jb↑j\}$ is not a regular set.
This is the way the pumping lemma is ordinarily used; it is very
useful to prove languages non-regular. It can't be used to prove
languages regular. Why?

\vfill\eject\end